1. Field of the Invention
The present invention relates to multicasting in switching apparatus for use, for example, in asynchronous transfer mode (ATM) networks. In particular the present invention relates to data units for use in such apparatus to implement multicasting.
2. Description of the Prior Art
FIG. 19 of the accompanying drawings shows parts of switching apparatus previously considered for use in an ATM network. The switching apparatus 1 includes sixty-four data units 20 to 263, each data unit having an input portion 40 to 463 and an output portion 60 to 663. For the sake of clarity only the input and output portions of the data units 20, 21, 22 and 263 are shown in FIG. 19. In FIG. 19, the output portion 6 of each data unit 2 is shown separately from the input portion 4 of the unit concerned, so as to clarify the operation of the apparatus, but it will be appreciated that both the input and output portions 4 and 6 form part of the same data unit 2.
Each data unit 2 is connected to one or more data input/output ports DP0 to DP127 of the switching apparatus; for example, as shown in FIG. 19, each data unit is connected to a pair of data ports DP.
The data ports DP of the FIG. 19 apparatus are connected to respective ATM communications lines, which typically each provide a large number of separate channels (virtual channels). Each ATM virtual channel carries data in the form of fixed-length cells.
The apparatus 1 further comprises a cross-connect switching unit 8 having as many input ports IP0 to IP63 and as many output ports OP0 to OP63 as there are data units 2. Each input portion 4 is connected to one of the input ports IP and each of the output portions 6 is connected to one of the output ports OP.
The cross-connect switching unit 8 is controllable selectively to provide connections between its input ports and its output ports. Up to 64 simultaneous connections, each between one of its input ports and one of its output ports, can be provided. For example, if data is received by the apparatus 1 at data port DP2 (the xe2x80x9csourcexe2x80x9d data port) that is to be routed to data port DP4 (the xe2x80x9cdestinationxe2x80x9d data port), the cross-connect switching unit 8 is configured to provide a connection between the input portion 41 of the data unit 21 (the xe2x80x9csource data unitxe2x80x9d having the source data port DP2 connected to it) to the output portion 62 of the data unit 22 (the xe2x80x9cdestination data unitxe2x80x9d) which has the destination data port DP4 connected to it. Thus, the source data unit 21 and the destination data unit 22 form a data-unit pair and are allocated a data transfer path within the apparatus for use in passing data from the source data unit of the pair to the destination data unit of the pair. At the same time, up to 63 other such data-unit pairs can be allocated respective data transfer paths by the switching unit 8 to enable data received at source data ports connected with the respective source data units of those pairs also to be routed through the switch to the respective destination data units of the pairs, those destination data units being connected with the relevant destination data ports.
Since it is possible for two (or more) source data ports to wish to communicate at the same time to the same destination data port, it is normal to make provision for some buffering of the data at some point within the switching apparatus, either within the data units 2 or in the cross-connect switching unit 8, or possibly in both. This buffering holds up the data of one of the two contending source data ports pending transfer to the intended destination data port of the data received at the other of those two contending source data ports.
Of the virtual channels connected to the data ports, some channels are so-called xe2x80x9cunicastxe2x80x9d channels, the cells of which are to be switched by the apparatus to just a single other virtual channel. However, other channels connected to the data ports may be so-called xe2x80x9cmulticastxe2x80x9d channels, the cells of which are to be switched by the apparatus to more than one other channel. Thus, to deal with cells received from such a multicast channel it is usually necessary to transfer the cells from the source data port to a plurality of destination data ports.
There are a number of ways in which provision can be made for such multicasting. For example, as described in more detail in our copending United Kingdom application no. 9617110.3, it is possible to operate the data units in xe2x80x9cmulticasting groupsxe2x80x9d, each group having a source data unit which outputs one or more cells to all of the destination data units of the group at the same time. In order to avoid contention at the output ports of the switching unit, it will generally only be possible for one or a limited number of such multicasting groups to be formed at the same time. Thus, in this method the data units have to be allocated multicasting opportunities individually or in small groups in turn, for example at predetermined time intervals.
However, this multicasting method remains relatively inefficient, since it is complex to control and arrange, for example from the software point of view, and, being prone to cell contention problems, may lead to cell loss unless significant buffering is provided in the apparatus.
In addition, just as with unicast channels, multicast channels may be used to carry different types of data traffic. For example, some multicast channels may be used to carry low-priority computer data files, whereas other multicast channels may be used to carry high-priority constant-bit-rate (CBR) traffic such as voice and video. All ATM channels, including multicast channels, must meet the quality of service (QoS) requirements specified at the time the channel concerned is set up. In particular, cell delays and cell delay variations (CDV) must be within agreed limits commensurate with the specified QoS requirements. There may be unicast and multicast channels, passing through the switching apparatus to the same destination data port, that have the same priority (QoS requirements). The allocation of multicasting opportunities at predetermined time intervals can result in the multicast channels receiving priority in the switching apparatus so that a multicast cell destined for a particular data port and received after a unicast cell for that same destination data port is nonetheless transferred to the destination data port before the unicast cell, even though the two cells have the same priority.
In effect, therefore, the cell sequence integrity for different virtual channels of the same priority cannot be guaranteed. By tending to accord higher priority to multicast channels in the switching apparatus, cell delays for unicast channels can build up elsewhere in the network which must be strenuously avoided as cell delays and cell delay variation have serious degrading effects on real-time traffic such as voice and video traffic. Voice traffic, for example, may be truncated and unwanted signals and undesirable sound effects may be introduced. Video traffic is even more susceptible to such delay/phase variations which manifest themselves as dropped picture elements, colour changes and other visual anomalies.
It may also be desired to make the switching apparatus xe2x80x9cself-routingxe2x80x9d so that data passes along a suitable route through the various components of the apparatus without every component having to have its routing of the data controlled directly by the switching controller, thereby reducing the control burden on the switching controller. The need to perform multicasting complicates design of the switching apparatus components and accordingly it is desirable to provide a multicasting method for use in such apparatus having self-routing components, in particular a self-routing switching unit, without over-complicating the designs of those components.
According to a first aspect of the present invention there is provided a data unit, for receiving data packets and delivering them to packet switching circuitry, including: packet storage means for causing the received data packets to be stored in memory means; packet registration means operable, when each data packet belonging to a predetermined first category of the data packets is received, to make an entry corresponding to the packet concerned in first register means and also operable, when each data packet belonging to a predetermined second category of the data packets is received, to make an entry corresponding to the packet concerned in second register means; multicast handling means operable, when such a received data packet is a multicast packet belonging to both the said first and second categories, to cause the packet registration means to make respective entries corresponding to the multicast packet concerned in both the first and second register means; and packet output means operable, for each of the said first and second register means, to read the entries in the register means concerned in the order in which they were made and, for each entry read, to read out the corresponding data packet from the memory means and output it.
In such a data unit, cell sequence integrity is ensured for unicast and multicast packets belonging to the same category, making it possible to meet reliably quality of service requirements for both unicast and multicast packets.
There may be further predetermined categories of the data packets in addition to the said first and second categories, in which case the data unit preferably has such register means for each different category of the data packets, and the said multicast handling means serve, when such a multicast packet is received, to cause the packet registration means to make such an entry corresponding to the packet concerned in the register means for each category to which the packet belongs.
Preferably, the received data packets are categorised according to their respective intended destinations after being output to the packet switching circuitry by the packet output means, and each said register means corresponds to a different such intended destination. For example, a plurality of the data units may be employed together in switching apparatus, with switching means (a switching fabric) interconnecting the units and serving to provide data transfer paths selectively between pairs of the data units. The intended destinations then correspond respectively to the different data units.
Each said register means preferably has a first-in first-out organisation, for example a queue. This makes it easy for the entries in the register means to be read in the order in which they were made, and hence increases speed and efficiency.
When the received data packet is a multicast packet, the packet storage means are preferably caused to store the multicast packet at a single location in the said memory means, and the said entry corresponding to the multicast packet, made by the packet registration means in the register means for each category to which the multicast packet belongs, includes a pointer to the said single location. This avoids the need to store a copy of the multicast packet for each of its intended destinations. Although an entry needs to be made in each appropriate register means, the entry has significantly less information than the packet itself, so that rapid registration of the packets is possible.
The said memory means and each said register means preferably form part of the same storage unit, for example a static RAM, which may be internal or external to the data unit itself. This avoids the need to provide many different memories. If the storage unit is external, its size can be chosen to suit the traffic requirements; heavy traffic applications will require a larger storage unit than low traffic applications. This affords flexibility and can help to control costs.
For each data packet that is a unicast packet belonging to just one of the said categories of data packets, the said entry corresponding to that unicast packet preferably includes at least some data of the packet itself. In other words, when the memory means and register means all form part of the same storage unit, there is no need for the entry corresponding to a unicast packet to be separate from the packet itself: they can both be made in a single xe2x80x9cdescriptorxe2x80x9d placed in the relevant register means (queue) when the unicast cell is received.
The said packet storage means preferably organise the said storage unit in data blocks and include free pool means, for registering those data blocks of the storage unit that are free for use, the packet storage means being operable, when a data packet is received, to allocate the packet one of the said data blocks registered by the said free pool means as being free for use; the data block allocated to such a unicast packet being re-registered by the free pool means when the said entry corresponding to that packet (e.g. the descriptor mentioned above) has been read by the packet output means from the register means in which it was made.
The use of such data blocks in this way allows the memory resources to be allocated dynamically when the unit is in use, which avoids the need to reserve fixed amounts of memory for each register means and for the memory means in advance.
In this case, the said multicast handling means are preferably operable to inhibit the re-registration by the free pool means of a data block allocated to a multicast packet until each one of the said entries corresponding to that multicast packet has been read by the packet output means. For example, the data of the said multicast packet may be stored in a multicast descriptor in the data block allocated to the packet. This multicast descriptor preferably includes multicast processed bits corresponding respectively to the different categories of data packets. The said multicast handling means are operable, when such a multicast packet is received, to preset to a first state the multicast processed bits corresponding respectively to the categories to which the multicast packet concerned belongs, whilst presetting the remaining multicast processed bits to a second state different from the said first state, and are also operable, when the entry corresponding to the multicast packet in one of the register means is read by the output means, to change the multicast processed bit corresponding to that register means to the said second state, and to cause the data block allocated to the multicast packet to be returned to the said free pool upon detecting that all of the said multicast processed bits have the said second state. This permits convenient handling of multicast descriptors.
In one preferred embodiment, each said entry corresponding to a multicast packet is made in a link descriptor stored in one of the said data blocks, and the entries corresponding respectively to at least two successive multicast packets received between two successive unicast packets can be stored in the same link descriptor. This avoids the need to create a new descriptor in each appropriate register means each time a multicast packet is received. As the entry may be a simple pointer to the relevant multicast descriptor, many entries can be accommodated in a single link descriptor, saving memory, and the speed of making the entry is very high. Thus, it may be possible to update all the register means before the next packet is received, so avoiding the need for extra buffering or congestion control procedures.
The received data packets may be sub-categorised according to their respective priorities. In this case, the register means for at least one category are preferably sub-divided into a plurality of sub-register means corresponding respectively to the different priority-sub-categories, the packet registration means being operable, when a data packet belonging to the said one category is received, to make the said entry corresponding to the data packet in that one of the said sub-register means which corresponds to the priority-sub-category to which the packet concerned belongs. The packet output means are operable to select the sub-register means in priority order and, for each selected sub-register means, to output the data packets whose respective corresponding entries are in the sub-register means concerned in the order in which those entries were made. This can ensure that higher-priority packets are output in preference to lower-priority ones but still keeps the correct packet sequence as between unicast and multicast packets belonging to the same (main) category, e.g. having the same intended destination.
The said output means are operable to attach a routing tag to each data packet output thereby, which routing tag includes information identifying the said intended destination of the packet. This can enable the switching fabric components to be self-routing. In one embodiment, the output means are operable to attach to each data packet output thereby a routing tag including information identifying the said intended destination of the next data packet to be output thereby. This xe2x80x9cfeed-forwardxe2x80x9d method can permit a self-routing component to set its configuration for the next packet as soon as the previous packet has been dealt with, so potentially reducing buffering requirements in the component.
The routing tag may be of fixed length as every packet output by the output meansxe2x80x94even one derived from a multicast received packetxe2x80x94has only one destination.
In one preferred embodiment the data unit is employed in ATM switching apparatus and the said data packets each comprise one or more ATM cells.
In this case, the said output means are preferably operable, when an entry corresponding to such a multicast packet is read from the register means corresponding to one of the said intended destinations of the packet, to include, in the header portion of the or each ATM cell of the packet output thereby, routing information corresponding to that intended destination. This enables the different output packets for the different destinations to have unique cell addresses.
In such ATM switching apparatus each data unit and the switching fabric components may operate asynchronously, but the data units and switching fabric components preferably operate synchronously to perform a series of switching cycles, and the apparatus preferably further comprises switching control means connected with the said data units for selecting the register means of each data unit from which one of the said entries is to be read by the output means of the unit concerned in each switching cycle. This can avoid contention problems in the apparatus and also enables the switching controller to allocate switching resources fairly, for example dynamically in dependence upon queue fill levels in the data units. The switching fabric components of such a synchronous switch may be essentially memory-less, for example a simple cross-connect switching unit may be used.
According to a second aspect of the present invention there is provided a method of multicasting data packets, for use in a data unit of packet switching apparatus, which method comprises: receiving data packets at the data unit and storing them in memory means; when each data packet belonging to a predetermined first category of the data packets is received, making an entry corresponding to the packet concerned in first register means and, when each data packet belonging to a predetermined second category of the data packets is received, making an entry corresponding to the packet concerned in second register means, and when such a received data packet is a multicast packet belonging to both the said first and second categories, making respective entries corresponding to the multicast packet concerned in both the first and second register means; and, for each of the said first and second register means, reading the entries in the register means concerned in the order in which they were made and, for each entry read, reading out the corresponding data packet from the memory means and outputting it from the data unit.
According to a third aspect of the present invention there is provided a cross-connect switching device, for switching data packets which include routing information, including: a plurality of ports; data transfer means selectively controllable to provide a plurality of data transfer paths at the same time, each path having an input port and an output port selected from the ports of the said plurality and serving to pass such a data packet received at its said input port to its said output port; and self-routing means operable, when such a data packet is received by the device at one of its said ports, to allocate the packet such a data transfer path having that port as its said input port and having as its said output port a further one of the ports selected by the self-routing means in dependence upon the said routing information.
In one embodiment, each said data packet includes routing information relating to that packet itself, but alternatively the data packet received at each port of the device may include routing information for the next data packet that is to be received by the port concerned, and the said self-routing means are operable to employ the routing information received with each data packet to allocate the data transfer path for the next data packet.